package Compation;

/**
 * 1453. 圆形靶内的最大飞镖数量
 * https://leetcode-cn.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/
 * 墙壁上挂着一个圆形的飞镖靶。现在请你蒙着眼睛向靶上投掷飞镖。
 *
 * 投掷到墙上的飞镖用二维平面上的点坐标数组表示。飞镖靶的半径为 r 。
 *
 * 请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。
 *
 * 示例 1：
 * 输入：points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
 * 输出：4
 * 解释：如果圆形的飞镖靶的圆心为 (0,0) ，半径为 2 ，所有的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 4 。
 * 示例 2：
 * 输入：points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
 * 输出：5
 * 解释：如果圆形的飞镖靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。
 * 示例 3：
 * 输入：points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
 * 输出：1
 * 示例 4：
 * 输入：points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
 * 输出：4
 *
 *
 * 提示：
 *
 * 1 <= points.length <= 100
 * points[i].length == 2
 * -10^4 <= points[i][0], points[i][1] <= 10^4
 * 1 <= r <= 5000
 */
public class numPoints {
    public int numPoints(int[][] points, int r) {
        if (points == null ||  points.length == 0) {
            return 0;
        }
        if (points.length == 1) {
            return 1;
        }
        int n = points.length;
        int result = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0];
                int y1 = points[i][1];
                int x2 = points[j][0];
                int y2 = points[j][1];
                double d = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
                if (d > 2 * r) continue; // 大于直径
                // 求中点坐标
                double midX = (x1 + x2) / 2.0;
                double midY = (y1 + y2) / 2.0;
                // 求圆心到中点连线的距离
                double h = Math.sqrt(r * r - d * d / 4);
                // 求AB的向量
                double v1 = x1 - x2;
                double v2 = y1 - y2;
                // (-v2/d, v1/d) (v2/d, -v1/d)
                double xc = midX - v2 / d * h;
                double yc = midY + v1 / d * h;
                result = Math.max(result, count(points, xc, yc, r));
                xc = midX + v2 / d * h;
                yc = midY - v1 / d * h;
                result = Math.max(result, count(points, xc, yc, r));
            }
        }
        return result;
    }

    private int count(int[][] points, double x, double y, int r) {
        int ans = 0;
        double eps = 1e-8;
        for (int[] point : points) {
            double dx = x - point[0];
            double dy = y - point[1];
            double d = dx * dx + dy * dy;
            if (d <= r * r + eps) ans++;
        }
        return ans;
    }
}
